from tools_algorithm import *


class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:

        h = {}

        def add(d, num, i):
            if i == len(num):
                return
            nm = num[i]
            if nm not in d:
                d[nm] = {}
            add(d[nm], num, i + 1)

        for num in arr1:
            add(h, str(num), 0)

        def find(d, num, i):
            if i == len(num):
                return 0
            nm = num[i]
            if nm in d:
                return find(d[nm], num, i + 1) + 1
            return 0

        ans = 0
        for num in arr2:
            ans = max(ans, find(h, str(num), 0))

        return ans


s = Solution()
print(s.longestCommonPrefix(arr1=[1, 10, 100], arr2=[1000]))
